# -*- coding:utf-8 -*-

"""
删除链表中的某个节点：
    （1）删除链表中的某个节点一定需要知道这个点的前继节点，所以需要一直有指针指向前继节点
    （2）伪删除，指复制一个和要删除节点值一样的节点，然后删除，这样就不必知道其真正的前继节点了
        只需要把prev -> next = prev -> next -> next
链表指针的鲁棒性：
    （1）当访问链表中某个节点curt.next时，一定要先判断curt是否为null
    （2）全部操作结束后判断是否有环；若有环，则其中一端为null
    Dummy Node
Dummy node（“哑节点”或“假人头结点”）：
    （1）Dummy node 是一个虚拟节点，也可以认为是标杆节点。
        Dummy node 就是在链表表头 head 前加一个节点指向 head，即 dummy -> head。
        Dummy node 的使用多针对单链表没有前向指针的问题，保证链表的 head 不会在删除操作中丢失。
    （2）使用 dummy node 来进行head的删除操作
        返回 dummy.next = 新的链表，删除head。
快慢指针：
    （1）快慢指的是指针向前移动的步长，每次移动的步长较大即为快，步长较小即为慢
        常用的快慢指针一般是在单链表中让快指针每次向前移动2，慢指针则每次向前移动1。
        快慢两个指针都从链表头开始遍历，于是快指针到达链表末尾的时候慢指针刚好到达中间位置，于是可以得到中间元素的值。
    （2）快速找出未知长度单链表的中间节点 
        设置两个指针 *fast、*slow 都指向单链表的头节点，其中*fast的移动速度是*slow的2倍，当*fast指向末尾节点的时候，slow正好就在中间了。
    （3）判断单链表是否有环 
        设置两个指针 *fast、*slow 都指向单链表的头节点，其中 *fast的移动速度是*slow的2倍。
        如果 *fast = NULL，说明该单链表 以 NULL结尾，不是循环链表；如果 *fast = *slow，则快指针追上慢指针，说明该链表是循环链表。
"""
class NodeCircle:
    def __init__(self, val):
        self.val = val
        self.next = None

    def has_circle(self, head):
        slow = head
        fast = head
        while (slow and fast):
            fast = fast.next
            slow = slow.next
            if fast:
                fast = fast.next
            if fast == slow:
                break
        if fast and slow and (fast == slow):
            return True
        else:
            return False